/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 38917
 * Date: 2025/6/4
 * Time: 22:28
 */

public class Solution {
    public Node copyRandomList(Node head) {
        if(head == null) return null;
        //1.复制链表
        Node cur = head;
        while(cur != null){
            Node newNode = new Node(cur.val);
            newNode.next = cur.next;
            cur.next = newNode;
            cur = newNode.next;
        }
        //2.构造新节点的random指向
        cur = head;
        while(cur != null){
            if(cur.random != null){
                cur.next.random = cur.random.next;
            }
            cur = cur.next.next;
        }
        //3.分离新旧链表
        Node pre = head;
        cur = head.next;
        Node result = cur;
        while(pre.next.next != null){
            pre.next = pre.next.next;
            cur.next = cur.next.next;
            pre = pre.next;
            cur = cur.next;
        }
        //4.处理旧链表的尾节点
        pre.next = null;
        return result;
    }
}